package com.topcoder.srm519;

import java.util.HashMap;

public class RequiredSubstrings {
	private final static int MOD = 1000000009;
	
	public int solve(String[] words, int C, int L) {
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		int S = 0;
		for (String word : words) {
			for (int i=0; i<=word.length(); i++) {
				if (!map.containsKey(word.substring(0, i))) {
					map.put(word.substring(0, i), S++);
				}
			}
		}
		
		int[] nextState = new int[S*26];
		for (String state : map.keySet()) {
			for (int i=0; i<26; i++) {
				String ns = state + (char)('a' + i);
				while (!map.containsKey(ns)) ns = ns.substring(1);
				nextState[26*map.get(state) + i] = map.get(ns);
			}
		}
		
		int[] stateAdd = new int[S];
		for (String state : map.keySet()) {
			int add = 0;
			for (int i=0; i<words.length; i++) {
				if (state.endsWith(words[i])) add |= 1<<i;
			}
			stateAdd[map.get(state)] = add;
		}
		
		long[][] count = new long[2][S<<6];
		count[0][0] = 1;
		for (int i=0; i<L; i++) {
			int cur = i%2;
			int next = 1 - cur;
			for (int s=0; s<(S<<6); s++) count[next][s] = 0;
			for (int s=0; s<(S<<6); s++) {
				if (count[cur][s] > 0) {
					for (int c=0; c<26; c++) {
						int ns = nextState[26*(s>>6) + c];
						int np = (s & 63) | stateAdd[ns];
						count[next][(ns<<6)|np] += count[cur][s];
					}
				}
			}
			for (int s=0; s<(S<<6); s++) count[next][s] %= MOD;
		}
		
		long result = 0;
		for (int s=0; s<(S<<6); s++) {
			if (Integer.bitCount(s&63) == C) result += count[L%2][s];
		}

		return (int) (result % MOD);
	}
}
